package com.java.linkedlist;

import java.util.Objects;

/**
 * 双向链表
 *
 * @author 19252
 */
public class DoubleLinkedListDemo {
    public static void main(String[] args) {
        DoubleHeroNode heroNode1 = new DoubleHeroNode(1, "宋江", "及时雨");
        DoubleHeroNode heroNode2 = new DoubleHeroNode(2, "卢俊义", "玉麒麟");
        DoubleHeroNode heroNode3 = new DoubleHeroNode(3, "吴用", "智多星");
        DoubleHeroNode heroNode4 = new DoubleHeroNode(4, "公孙胜", "入云龙");
        DoubleLinkedList doubleLinkedList = new DoubleLinkedList();

        System.out.println("================> 添加演示 <=================");
//        doubleLinkedList.addNode(heroNode1);
//        doubleLinkedList.addNode(heroNode2);
//        doubleLinkedList.addNode(heroNode3);
//        doubleLinkedList.addNode(heroNode3);
//        doubleLinkedList.addNode(heroNode4);
        // 顺序添加演示
        doubleLinkedList.addNodeByNo(heroNode1);
        doubleLinkedList.addNodeByNo(heroNode3);
        doubleLinkedList.addNodeByNo(heroNode2);
        doubleLinkedList.addNodeByNo(heroNode4);
        doubleLinkedList.addNodeByNo(heroNode2);

        // 两种添加混合使用测试
//        doubleLinkedList.addNode(heroNode2);
//        doubleLinkedList.addNode(heroNode3);
//        doubleLinkedList.addNodeByNo(heroNode1);
//        doubleLinkedList.addNode(heroNode4);
//        doubleLinkedList.addNode(heroNode2);
        doubleLinkedList.showDoubleLinkedList();
        System.out.println("================> 修改演示 <=================");
        doubleLinkedList.updateNode(new DoubleHeroNode(2, "玉麒麟", "卢俊义"));
        doubleLinkedList.showDoubleLinkedList();
        System.out.println("================> 删除演示 <=================");
        doubleLinkedList.deleteNode(1);
        doubleLinkedList.showDoubleLinkedList();
    }
}

/**
 * 双向链表
 */
class DoubleLinkedList {

    /**
     * 双向链表空的头结点
     */
    private DoubleHeroNode head = new DoubleHeroNode();

    public DoubleHeroNode getHead() {
        return head;
    }

    /**
     * 双向链表添加节点
     * 添加节点（不考虑节点的编号顺序）
     * 1. 先找到最后的一个指向为空的节点
     * 2. 再将最后的节点指向（next = new heroNode）要添加的那个节点
     */
    public void addNode(DoubleHeroNode heroNode) {
        // 首先遍历节点
        DoubleHeroNode temp = head;
        // 判断 temp.getNext() 是否为空，为空则是最后一个节点
        while (Objects.nonNull(temp.getNext())) {
            temp = temp.getNext();
            if (temp.getNo() == heroNode.getNo()){
                System.out.println("该节点已存在，不能再添加！");
                return;
            }

        }
        // 为空，再将此时的next 指向 要添加的节点
        // 再将，添加进来的节点 pre 指向temp
        temp.setNext(heroNode);
        heroNode.setPre(temp);
    }

    /**
     * 添加链表中的节点按照，no 排序
     *
     * @param heroNode 链表的节点
     */
    public void addNodeByNo(DoubleHeroNode heroNode) {
        // 首先获取链表的头结点
        DoubleHeroNode temp = head;
        // 第一结点，是否为空判断
        boolean flag = Objects.nonNull(temp.getNext());
        while (flag) {
            // 重复节点判断
            // 从头结点开始
            if (temp.getNo() == heroNode.getNo()) {
                System.out.println("该节点已存在，不能再添加！");
                return;
            }
            // 同时判断两个节点的no，比较，在进行插入
            if (temp.getNo() < heroNode.getNo() && heroNode.getNo() < temp.getNext().getNo()) {
                heroNode.setNext(temp.getNext());
                temp.setNext(heroNode);
                heroNode.getNext().setPre(heroNode);
                heroNode.setPre(temp);
                return;
            }
            temp = temp.getNext();
            // 判断该节点的下一节点是否为空
            flag = Objects.nonNull(temp.getNext());
        }
        // 直接置为下一节点
        heroNode.setNext(temp.getNext());
        temp.setNext(heroNode);
        heroNode.setPre(temp);
    }

    /**
     * 双向链表的删除，可以找到该节点本身直接进行删除
     */
    public void deleteNode(int no) {
        DoubleHeroNode temp = head;
        // 链表非空判断
        boolean flag = Objects.nonNull(temp.getNext());
        while (flag) {
            temp = temp.getNext();
            flag = Objects.nonNull(temp.getNext());
            if (temp.getNo() == no) {
                temp.getPre().setNext(temp.getNext());
                if (flag){
                    // 如果这个节点不是最后一个节点,此时该节点才有下一节点
                    temp.getNext().setPre(temp.getPre());
                }
                return;
            }
        }
        System.out.println("你要删除的节点不存在！");
    }

    /**
     * 修改节点
     *
     * @param heroNode 要修改的节点
     */
    public void updateNode(DoubleHeroNode heroNode) {
        DoubleHeroNode temp = head;
        boolean flag = Objects.nonNull(temp.getNext());
        while (flag) {
            temp = temp.getNext();
            if (temp.getNo() == heroNode.getNo()) {
                temp.setName(heroNode.getName());
                temp.setNickname(heroNode.getNickname());
                // 修改完毕，直接退出
                return;
            }
            // 继续循环遍历
            flag = Objects.nonNull(temp.getNext());
        }
        // 链表为空
        System.out.println("你要修改的节点不存在！");
    }

    /**
     * 双向链表的顺序遍历
     */
    public void showDoubleLinkedList(){
        // 判断链表是否为空
        DoubleHeroNode temp = head;
        boolean flag = Objects.isNull(temp.getNext());
        if (flag) {
            System.out.println("链表为空！");
        } else {
            temp = head.getNext();
            flag = Objects.nonNull(temp);
            while (flag) {
                System.out.println(temp);
                temp = temp.getNext();
                flag = Objects.nonNull(temp);
            }
        }
    }
}

/**
 * 双向链表节点
 */
class DoubleHeroNode {

    /**
     * 下列字段初始值都为空
     */
    private int no;
    private String name;
    private String nickname;
    /**
     * 指向下一个节点
     */
    private DoubleHeroNode next = null;
    /**
     * 指向前一个节点
     */
    private DoubleHeroNode pre = null;

    public DoubleHeroNode() {
    }

    public DoubleHeroNode(int no, String name, String nickname) {
        this.no = no;
        this.name = name;
        this.nickname = nickname;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public String getNickname() {
        return nickname;
    }

    public void setNickname(String nickname) {
        this.nickname = nickname;
    }

    public DoubleHeroNode getNext() {
        return next;
    }

    public void setNext(DoubleHeroNode next) {
        this.next = next;
    }

    public DoubleHeroNode getPre() {
        return pre;
    }

    public void setPre(DoubleHeroNode pre) {
        this.pre = pre;
    }

    @Override
    public String toString() {
        return "DoubleHeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickname='" + nickname + '\'' +
                '}';
    }
}
